Nguồn gốc của NSA có thể coi bắt đầu từ một tổ chức thiết lập bên trong Bộ quốc phòng Hoa Kỳ có tên là Cơ quan an ninh lực lượng vũ trang (tiếng Anh: Armed Forces Security Agency, viết tắt AFSA) đặt dưới sự chỉ đạo của Bộ tổng tham mưu (Joint Chiefs of Staff) thành lập vào ngày 20 tháng 5 năm 1949. AFSA có nhiệm vụ chỉ đạo các hoạt động tình báo điện tử của các bộ phận tình báo bao gồm: Cơ quan an ninh quân sự (Army Security Agency), Bộ phận an ninh hải quân (Naval Security Group), và Cục an ninh không quân (Air Force Security Service). Tuy nhiên cơ quan này có rất ít quyền lực và thiếu các cơ chế phối hợp trung tâm. NSA ra đời từ một bản ghi nhớ ngày 10 tháng 10 năm 1951 gửi từ giám đốc CIA Walter Bedell Smith tới James B. Lay, bí thư thường trực của Hội đồng an ninh quốc gia. Ban ghi nhớ nêu rõ: "sự quản lý và phối hợp các hoạt động thu thập và xử lý thông tin tình báo truyền thông tỏ ra kém hiệu quả" và đề nghị một cuộc khảo sát về các hoạt động tình báo truyền thông. Đề nghị được phê chuẩn vào ngày 13 tháng 12 năm 1951 và các nghiên cứu được cho phép vào ngày 28 tháng 12 năm 1951 và báo cáo được hoàn thành vào 13 tháng 6 năm 1952. Được biết đến dưới tên " báo cáo hội đồng Brownell" theo tên của chủ tịch hội đồng Herbert Brownell, bản báo cáo đã tóm lược lịch sử các hoạt động tình báo truyền thông của Hoa Kỳ và đề xuất yêu cầu về chỉ đạo và phối hợp các hoạt động này ở mức độ quốc gia. NSA đã được thành lập với phạm vi vượt qua giới hạn trong lĩnh vực quân sự.

Việc thành lập NSA được phê chuẩn trong một bức thư của tổng thống Harry S. Truman vào tháng 6 năm 1952. NSA được chính thức thành lập qua một chỉ thị số 9 của Hội đồng an ninh quốc gia (NSCID) vào ngày 24 tháng 10 năm 1952 và bắt đầu hoạt động từ ngày 4 tháng 11 năm 1952. Bản thân bức thư của tổng thống Truman cũng là thông tin mật và được giữ bí mật trước công chúng nhiều năm sau đó.